Usenet 1993 July/InfoMagic USENET CD-ROM July 1993.ISO/sources/misc/volume11/quadtree/part01

Text File | 1990-04-03 | 23.4 KB | 871 lines

Newsgroups: comp.sources.misc
subject: v11i092: Quadtree image encoder/viewer
From: [e-mail] (Robert Steven Glickstein)
Sender: [e-mail] (Brandon S. Allbery - comp.sources.misc)

Posting-number: Volume 11, Issue 92
Submitted-by: [e-mail] (Robert Steven Glickstein)
Archive-name: quadtree/part01

This package encodes bitmaps as "quadtrees."  A quadtree viewer for X11
is included.  See the README file for more information.



---- Enclosure ----
#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#        "End of shell archive."
# Contents:  README Makefile quadtree.c quadtree.h ras2qt.c xqtdisp.c
# Wrapped by [e-mail] on Fri Mar 30 11:27:15 1990
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f README -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"README\"
else
echo shar: Extracting \"README\" \(3905 characters\)
sed "s/^X//" >README <<'END_OF_README'
XQUADTREE IMAGES by Bob Glickstein
X
XA ``quadtree'' is a means of encoding an image as a tree structure.
XEach node of the tree has up to four children.  The root node
Xrepresents the entire image; its children represent the four quadrants
Xof the entire image; their children represent the sixteen
Xsubquadrants; the children of those represent the sixty-four
Xsub-subquadrants, and so on.
X
XA leaf node corresponds to a single pixel, and is marked with the
Xcolor of that pixel (in this implementation, black or white only).  If
Xa non-leaf node has two or more children of the same color, then that
Xcolor is stored in the parent and the children are deleted.  Thus, if
Xan entire quadrant (subquadrant, sub-subquadrant, etc.) of the image
Xis white, that information can be stored in a single quadtree node,
Xand all of the children of that node can be removed.
X
XFor certain images, this encoding yields enormous savings in storage
Xsize.  Such images are typically line drawings or other bitmaps with
Xseveral areas of solid black or white.  Images with a lot of dithering
Xor stippling, such as scanned images, tend to yield little or no
Xsavings in space.
X
XAn amusing aspect of quadtrees is that they can be displayed according
Xto a depth-first or a breadth-first traversal of the tree.  In a
Xdepth-first traversal, first the prodemonant color of the entire image
Xis displayed; then the predominant color of the first quadrant is
Xdisplayed; then the predominant color of the first subquadrant of the
Xfirst quadrant, and so on.  The user can watch the quadrants and
Xsubquadrants being drawn.  A breadth-first traversal, however, is much
Xmore interesting.  Since it displays first the predominant color of
Xthe entire image, followed by the predominant colors of the four major
Xquadrants, followed by the predominant colors or the sixteen
Xsubquadrants, and so on, the effect is one of a gradually resolving
Ximage with finer and finer detail at each step.
X
X-----
X
XIncluded are two programs, ras2qt and xqtdisp.
X
XRas2qt is a filter which reads a raster on the standard input and
Xproduces a quadtree on the standard output, as in:
X
X    ras2qt < input.cmuwm > output.qt
X
XThe input raster is in CMU WM format.  Jeff Poskanzer's latest
XPortable Bitmap package (pbmplus, available on X11r4) includes filters
Xfor converting images to cmuwm format.
X
X    (some sequence of filters) | pbmtocmuwm | ras2qt > output.qt
X
XExpect ras2qt to spend several silent and intent seconds calculating
Xand writing the quadtree.
X
XXqtdisp is a quadtree viewer for X11.  It can be used as:
X
X    xqtdisp quadtree-file
X
Xin which case it will display the image depth-first; or as:
X
X    xqtdisp -b quadtree-file
X
Xin which case it will display the image breadth-first.  In both cases,
Xthe program requires several seconds to parse the quadtree before
Xcreating a window for displaying the image.  The user will be prompted
Xto press ENTER to begin displaying, and, when the traversal is
Xcompleted, will again be asked to press ENTER to exit the program.
X
XXqtdisp requires a lot of memory, especially in the breadth-first
Xcase.  For breadth-first traversals of large (> 70k) quadtrees, it may
Xbe necessary to do an ``unlimit'' first (csh users only), as in:
X
X    (unlimit; xqtdisp -b large-quadtree)
X
X-----
X
XThis software was written by Bob Glickstein ([e-mail]).  It
Xis in the public domain and may be freely copied, modified and
Xdistributed.  I provide no warranty for, and assume no responsibility
Xfor this software.  I'd like to hear from anyone with ideas or
Xcomments.
X
X-----
X
XComing soon:
X
X    - pbmtoqt
X    - qttopbm
X    - man pages
X    - sample quadtrees
X    - Faster execution
X
X-----
X
XNote that the routine QT_Bitmap_Read (in quadtree.c) makes an
Xassumption about the byte order of your machine when reading the width
Xand height of the raster.  You may need to modify this section if your
Xmachine does not store 32-bit integers in most-significant-byte-first
Xorder.
END_OF_README
if test 3905 -ne `wc -c <README`; then
    echo shar: \"README\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f Makefile -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"Makefile\"
else
echo shar: Extracting \"Makefile\" \(825 characters\)
sed "s/^X//" >Makefile <<'END_OF_Makefile'
XDESTDIR = /afs/andrew.cmu.edu/usr12/bobg
XBINDIR = bin
X
XINSTALL = install
X
XINSTFLAGS = -c -o bobg -s
X
Xall: ras2qt xqtdisp
X
Xinstall: all
X    $(INSTALL) $(INSTFLAGS) ras2qt $(DESTDIR)/$(BINDIR)
X    $(INSTALL) $(INSTFLAGS) xqtdisp $(DESTDIR)/$(BINDIR)
X
Xras2qt: ras2qt.o quadtree.o
X    cc -o ras2qt ras2qt.o quadtree.o
X
Xras2qt.o: ras2qt.c quadtree.h
X    cc -O -I. -c ras2qt.c
X
Xquadtree.o: quadtree.c quadtree.h
X    cc -O -I. -c quadtree.c
X
Xxqtdisp.o: xqtdisp.c quadtree.h
X    cc -O -I. -c xqtdisp.o xqtdisp.c
X
Xxqtdisp: xqtdisp.o quadtree.o
X    cc -o xqtdisp xqtdisp.o quadtree.o -lX11
X
Xclean:
X    -rm -f xqtdisp ras2qt *.o *.BAK *.CKP *~ a.out mon.out gmon.out core quadtree.shar
X
Xquadtree.shar: README Makefile quadtree.c quadtree.h ras2qt.c xqtdisp.c
X    -rm -f quadtree.shar
X    shar README Makefile quadtree.c quadtree.h ras2qt.c xqtdisp.c > quadtree.shar
END_OF_Makefile
if test 825 -ne `wc -c <Makefile`; then
    echo shar: \"Makefile\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f quadtree.c -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"quadtree.c\"
else
echo shar: Extracting \"quadtree.c\" \(7638 characters\)
sed "s/^X//" >quadtree.c <<'END_OF_quadtree.c'
X#include <stdio.h>
X#include <quadtree.h>
X
X#define ColorsAgree(c1,c2) ((c1)?(c2):(!(c2)))
X
Xstatic char     BitBuffer;
Xstatic int      BitPos;
X
Xextern char    *malloc();
X
Xint             QT_Bitmap_Bit(b, x, y)
XQT_Bitmap_t    *b;
Xint             x, y;
X{
X    int             index, byte, offset;
X
X    index = (y + b->y) * b->fullwidth + (x + b->x);
X    byte = index / 8;
X    offset = index % 8;
X    return (b->bits[byte] & (1 << offset));
X}
X
Xvoid            QT_Bitmap_SetBit(b, x, y, val)
XQT_Bitmap_t    *b;
Xint             x, y, val;
X{
X    int             index, byte, offset;
X
X    index = (y + b->y) * b->fullwidth + (x + b->x);
X    byte = index / 8;
X    offset = index % 8;
X    if (val)
X    b->bits[byte] |= (1 << offset);
X    else
X    b->bits[byte] &= ~(1 << offset);
X}
X
Xint             QT_Bitmap_Init(b, x, y, width, height, ref)
XQT_Bitmap_t    *b;
Xint             width, height;
XQT_Bitmap_t    *ref;
X{
X    b->x = x;
X    b->y = y;
X    b->width = width;
X    b->height = height;
X    if (ref) {
X    b->x += ref->x;
X    b->y += ref->y;
X    b->bits = ref->bits;
X    b->fullwidth = ref->fullwidth;
X    b->fullheight = ref->fullheight;
X    return (0);
X    }
X    b->fullwidth = width;
X    b->fullheight = height;
X    if (b->bits = malloc(width * height / 8 + 1)) {
X    bzero(b->bits, width * height / 8 + 1);
X    return (0);
X    }
X    return (1);
X}
X
XQT_TreeNode_t  *QT_TreeNode_New(color, ul, ur, ll, lr)
Xint             color;
XQT_TreeNode_t  *ul, *ur, *ll, *lr;
X{
X    QT_TreeNode_t  *result = (QT_TreeNode_t *) malloc(sizeof(QT_TreeNode_t));
X
X    if (result) {
X    result->color = color;
X    result->children[0] = ul;
X    result->children[1] = ur;
X    result->children[2] = ll;
X    result->children[3] = lr;
X    }
X    return (result);
X}
X
Xvoid            QT_TreeNode_Destroy(node)
XQT_TreeNode_t  *node;
X{
X    int             i;
X    QT_TreeNode_t  *child;
X
X    for (i = 0; i < 4; ++i) {
X    if (child = QT_TreeNode_Child(node, i))
X        QT_TreeNode_Destroy(child);
X    }
X    free(node);
X}
X
Xstatic int      TreeAgrees(color, node)
Xint             color;
XQT_TreeNode_t  *node;
X{
X    return ((ColorsAgree(color, QT_TreeNode_Color(node)))
X        && ((!(QT_TreeNode_Child(node, 0)))
X        || TreeAgrees(color, QT_TreeNode_Child(node, 0)))
X        && ((!(QT_TreeNode_Child(node, 1)))
X        || TreeAgrees(color, QT_TreeNode_Child(node, 1)))
X        && ((!(QT_TreeNode_Child(node, 2)))
X        || TreeAgrees(color, QT_TreeNode_Child(node, 2)))
X        && ((!(QT_TreeNode_Child(node, 3)))
X        || TreeAgrees(color,
X                  QT_TreeNode_Child(node, 3))));
X}
X
XQT_TreeNode_t  *QT_BitmapToTree(b)
XQT_Bitmap_t    *b;
X{
X    QT_Bitmap_t     ulbm, urbm, llbm, lrbm;
X    QT_TreeNode_t  *ulqt, *urqt, *llqt, *lrqt;
X    int             h = QT_Bitmap_Height(b), w = QT_Bitmap_Width(b), h2, w2;
X    int             ones = 0, zeroes = 0, color;
X
X    switch (w * h) {
X    case 0:
X        return 0;
X    case 1:
X        return (QT_TreeNode_New(QT_Bitmap_Bit(b, 0, 0),
X                    0, 0, 0, 0));
X    }
X    /* It's a non-trivial bitmap */
X    h2 = h >> 1;
X    w2 = w >> 1;
X    (void) QT_Bitmap_Init(&ulbm, 0, 0, w2, h2, b);
X    (void) QT_Bitmap_Init(&urbm, w2, 0, w - w2, h2, b);
X    (void) QT_Bitmap_Init(&llbm, 0, h2, w2, h - h2, b);
X    (void) QT_Bitmap_Init(&lrbm, w2, h2, w - w2, h - h2, b);
X    ulqt = QT_BitmapToTree(&ulbm);
X    urqt = QT_BitmapToTree(&urbm);
X    llqt = QT_BitmapToTree(&llbm);
X    lrqt = QT_BitmapToTree(&lrbm);
X    if (ulqt) {
X    if (QT_TreeNode_Color(ulqt))
X        ++ones;
X    else
X        ++zeroes;
X    }
X    if (urqt) {
X    if (QT_TreeNode_Color(urqt))
X        ++ones;
X    else
X        ++zeroes;
X    }
X    if (llqt) {
X    if (QT_TreeNode_Color(llqt))
X        ++ones;
X    else
X        ++zeroes;
X    }
X    if (lrqt) {
X    if (QT_TreeNode_Color(lrqt))
X        ++ones;
X    else
X        ++zeroes;
X    }
X    color = (ones > zeroes) ? 1 : 0;
X    if (ulqt) {
X    if (TreeAgrees(color, ulqt)) {
X        QT_TreeNode_Destroy(ulqt);
X        ulqt = 0;
X    }
X    }
X    if (urqt) {
X    if (TreeAgrees(color, urqt)) {
X        QT_TreeNode_Destroy(urqt);
X        urqt = 0;
X    }
X    }
X    if (llqt) {
X    if (TreeAgrees(color, llqt)) {
X        QT_TreeNode_Destroy(llqt);
X        llqt = 0;
X    }
X    }
X    if (lrqt) {
X    if (TreeAgrees(color, lrqt)) {
X        QT_TreeNode_Destroy(lrqt);
X        lrqt = 0;
X    }
X    }
X    return (QT_TreeNode_New(color, ulqt, urqt, llqt, lrqt));
X}
X
Xstatic void     BitWrite(bit, fp)
Xint             bit;
XFILE           *fp;
X{
X    if (bit)
X    BitBuffer |= (1 << BitPos);
X    else
X    BitBuffer &= ~(1 << BitPos);
X    if ((--BitPos) < 0) {
X    BitPos = 7;
X    fputc(BitBuffer, fp);
X    }
X}
X
X#define BitFlush(fp) (fputc(BitBuffer,(fp)))
X
Xstatic void     QT_TreeNode_Write(fp, node, fmt)
XFILE           *fp;
XQT_TreeNode_t  *node;
Xchar            fmt;
X{
X    int             i;
X    QT_TreeNode_t  *child;
X
X    switch (fmt) {
X    case 0:
X        BitWrite(0, fp);
X        BitWrite(QT_TreeNode_Color(node), fp);
X        for (i = 0; i < 4; ++i) {
X        if (child = QT_TreeNode_Child(node, i))
X            QT_TreeNode_Write(fp, child, fmt);
X        else
X            BitWrite(1, fp);
X        }
X        break;
X    case 1:
X        BitWrite(0, fp);
X        BitWrite(QT_TreeNode_Color(node), fp);
X        if (QT_TreeNode_Child(node, 0)
X        || QT_TreeNode_Child(node, 1)
X        || QT_TreeNode_Child(node, 2)
X        || QT_TreeNode_Child(node, 3)) {
X        for (i = 0; i < 4; ++i) {
X            if (child = QT_TreeNode_Child(node, i))
X            QT_TreeNode_Write(fp, child, fmt);
X            else {
X            BitWrite(1, fp);
X            BitWrite(0, fp);
X            }
X        }
X        }
X        else {
X        BitWrite(1, fp);
X        BitWrite(1, fp);
X        }
X        break;
X    }
X}
X
Xvoid            QT_Tree_Write(fp, node, fmt, w, h)
XFILE           *fp;
XQT_TreeNode_t  *node;
Xchar            fmt;
Xshort           w, h;
X{
X    BitPos = 7;
X    fputc(fmt, fp);
X    fputc(w % 256, fp);
X    fputc(w / 256, fp);
X    fputc(h % 256, fp);
X    fputc(h / 256, fp);
X    QT_TreeNode_Write(fp, node, fmt);
X    BitFlush(fp);
X}
X
Xstatic int      BitRead(fp)
XFILE           *fp;
X{
X    if ((--BitPos) < 0) {
X    BitPos = 7;
X    BitBuffer = fgetc(fp);
X    }
X    return (BitBuffer & (1 << BitPos));
X}
X
Xstatic QT_TreeNode_t *QT_TreeNode_Read(fp, fmt, extra)
XFILE           *fp;
Xchar            fmt;
Xint            *extra;
X{
X    int             bit = BitRead(fp), bit2, nochildren, dummy;
X    QT_TreeNode_t  *ul, *ur, *ll, *lr;
X
X    switch (fmt) {
X    case 0:
X        if (bit) {
X        return (0);
X        }
X        bit = BitRead(fp);
X        ul = QT_TreeNode_Read(fp, fmt, &dummy);
X        ur = QT_TreeNode_Read(fp, fmt, &dummy);
X        ll = QT_TreeNode_Read(fp, fmt, &dummy);
X        lr = QT_TreeNode_Read(fp, fmt, &dummy);
X        return (QT_TreeNode_New(bit, ul, ur, ll, lr));
X    case 1:
X        bit2 = BitRead(fp);
X        if (bit) {
X        *extra = bit2;
X        return (0);
X        }
X        ul = QT_TreeNode_Read(fp, fmt, &nochildren);
X        if ((!ul) && nochildren)
X        return (QT_TreeNode_New(bit2, 0, 0, 0, 0));
X        ur = QT_TreeNode_Read(fp, fmt, &dummy);
X        ll = QT_TreeNode_Read(fp, fmt, &dummy);
X        lr = QT_TreeNode_Read(fp, fmt, &dummy);
X        return (QT_TreeNode_New(bit2, ul, ur, ll, lr));
X    }
X}
X
XQT_TreeNode_t  *QT_Tree_Read(fp, w, h)
XFILE           *fp;
Xshort          *w, *h;
X{
X    char            fmt = fgetc(fp);
X    int             dummy;
X
X    BitPos = 0;
X    *w = fgetc(fp);
X    *w += fgetc(fp) * 256;
X    *h = fgetc(fp);
X    *h += fgetc(fp) * 256;
X    return (QT_TreeNode_Read(fp, fmt, &dummy));
X}
X
Xint             QT_Bitmap_Read(b, fp)  /* B is an *uninitialized* bitmap */
XQT_Bitmap_t    *b;
XFILE           *fp;
X{
X    int             x, y, c;
X    char            buf[4];
X    long            w, h;
X
X    fread(buf, 4, 1, fp);
X    fread(&w, 4, 1, fp);
X    fread(&h, 4, 1, fp);
X    fread(buf, 2, 1, fp);
X    if (QT_Bitmap_Init(b, 0, 0, (int) w, (int) h, 0))
X    return (1);
X    BitPos = -1;
X    for (y = 0; y < h; ++y) {
X    for (x = 0; x < w; ++x) {
X        c = BitRead(fp);
X        QT_Bitmap_SetBit(b, x, y, !c);
X    }
X    BitPos = -1;
X    }
X    return (0);
X}
END_OF_quadtree.c
if test 7638 -ne `wc -c <quadtree.c`; then
    echo shar: \"quadtree.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f quadtree.h -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"quadtree.h\"
else
echo shar: Extracting \"quadtree.h\" \(1318 characters\)
sed "s/^X//" >quadtree.h <<'END_OF_quadtree.h'
Xtypedef struct {
X    short           x, y, width, height, fullwidth, fullheight;
X    char           *bits;
X}               QT_Bitmap_t;
X
Xtypedef struct _QT_TreeNode {
X    short           color;
X    struct _QT_TreeNode *children[4];
X}               QT_TreeNode_t;
X
X#define QT_Bitmap_Width(b) ((b)->width)
X#define QT_Bitmap_Height(b) ((b)->height)
X
X#define QT_TreeNode_Color(t) ((t)->color)
X#define QT_TreeNode_Child(t,n) ((t)->children[n])
X#define QT_TreeNode_UpperLeft(t) (QT_TreeNode_Child((t),0))
X#define QT_TreeNode_UpperRight(t) (QT_TreeNode_Child((t),1))
X#define QT_TreeNode_LowerLeft(t) (QT_TreeNode_Child((t),2))
X#define QT_TreeNode_LowerRight(t) (QT_TreeNode_Child((t),3))
X#define QT_TreeNode_SetColor(t,c) (((t)->color)=(c))
X#define QT_TreeNode_SetUpperLeft(t,v) (((t)->children[0])=(v))
X#define QT_TreeNode_SetUpperRight(t,v) (((t)->children[1])=(v))
X#define QT_TreeNode_SetLowerLeft(t,v) (((t)->children[2])=(v))
X#define QT_TreeNode_SetLowerRight(t,v) (((t)->children[3])=(v))
X
Xextern QT_TreeNode_t *QT_BitmapToTree();
Xextern int      QT_Bitmap_Bit();
Xextern int      QT_Bitmap_Init();
Xextern int      QT_Bitmap_Read();
Xextern void     QT_Bitmap_SetBit();
Xextern void     QT_TreeNode_Destroy();
Xextern QT_TreeNode_t *QT_TreeNode_New();
Xextern QT_TreeNode_t *QT_Tree_Read();
Xextern void     QT_Tree_Write();
END_OF_quadtree.h
if test 1318 -ne `wc -c <quadtree.h`; then
    echo shar: \"quadtree.h\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f ras2qt.c -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"ras2qt.c\"
else
echo shar: Extracting \"ras2qt.c\" \(535 characters\)
sed "s/^X//" >ras2qt.c <<'END_OF_ras2qt.c'
X#include <stdio.h>
X#include <quadtree.h>
X
Xextern int      optind;
Xextern char    *optarg;
X
Xmain(argc, argv)
X{
X    QT_Bitmap_t     Bitmap;
X    QT_TreeNode_t  *root;
X    int             c;
X    char            fmt = 0;
X
X    while ((c = getopt(argc, argv, "12")) != EOF) {
X    switch (c) {
X        case '1':
X        case '2':
X        fmt = c - '1';
X        break;
X    }
X    }
X    QT_Bitmap_Read(&Bitmap, stdin);
X    root = QT_BitmapToTree(&Bitmap);
X    QT_Tree_Write(stdout, root, fmt,
X          QT_Bitmap_Width(&Bitmap),
X          QT_Bitmap_Height(&Bitmap));
X    exit(0);
X}
END_OF_ras2qt.c
if test 535 -ne `wc -c <ras2qt.c`; then
    echo shar: \"ras2qt.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f xqtdisp.c -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"xqtdisp.c\"
else
echo shar: Extracting \"xqtdisp.c\" \(5375 characters\)
sed "s/^X//" >xqtdisp.c <<'END_OF_xqtdisp.c'
X#include <stdio.h>
X#include <quadtree.h>
X#include <X11/Xlib.h>
X#include <X11/Xatom.h>
X#include <X11/Xutil.h>
X
Xextern char    *getenv(), *optarg, *malloc();
Xextern int      optind;
Xextern FILE    *fopen();
X
XDisplay        *QTDisplay;
XWindow          QTWindow;
XGC              WhiteRegion, BlackRegion;
Xint             Verbose;
X
Xstruct Qentry {
X    QT_TreeNode_t  *node;
X    struct Qentry  *next, *prev;
X    short           x, y, width, height, parent;
X}              *Head, *Tail, *Freelist;
X
X#define ColorsAgree(c1,c2) ((c1)?(c2):(!(c2)))
X
Xstruct Qentry  *NewQentry()
X{
X    struct Qentry  *result, *ptr;
X    int             i;
X
X    if (result = Freelist) {
X    Freelist = result->next;
X    return (result);
X    }
X    result = (struct Qentry *) malloc(64 *
X                      (sizeof(struct Qentry)));
X    for (i = 0, ptr = result; i < 63; ++ptr, ++i) {
X    ptr->next = ptr + 1;
X    }
X    ptr->next = Freelist;
X    Freelist = result->next;
X    return (result);
X}
X
Xvoid            ReleaseQentry(qe)
Xstruct Qentry  *qe;
X{
X    qe->next = Freelist;
X    Freelist = qe;
X}
X
Xmain(argc, argv)
Xint             argc;
Xchar          **argv;
X{
X    int             c, breadth = 0, screen;
X    short           width, height;
X    QT_TreeNode_t  *Tree;
X    FILE           *fp;
X    char           *displayname;
X    Window          rwindow;
X    XGCValues       gcv;
X
X    Freelist = 0;
X    Verbose = 0;
X    while ((c = getopt(argc, argv, "bdv")) != EOF) {
X    switch (c) {
X        case 'b':
X        breadth = 1;
X        break;
X        case 'd':
X        breadth = 0;
X        break;
X        case 'v':
X        ++Verbose;
X        break;
X    }
X    }
X    if (!(fp = fopen(argv[optind], "r"))) {
X    exit(1);
X    }
X    Tree = QT_Tree_Read(fp, &width, &height);
X    if (!(displayname = getenv("DISPLAY")))
X    displayname = ":0";
X    QTDisplay = XOpenDisplay(displayname);
X    screen = DefaultScreen(QTDisplay);
X    rwindow = RootWindow(QTDisplay, screen);
X    QTWindow = XCreateSimpleWindow(QTDisplay, rwindow,
X                   0, 0, width, height,
X                   1, WhitePixel(QTDisplay, screen),
X                   BlackPixel(QTDisplay, screen));
X    XMapWindow(QTDisplay, QTWindow);
X    XSync(QTDisplay, 0);
X    gcv.foreground = WhitePixel(QTDisplay, screen);
X    gcv.function = GXset;
X    WhiteRegion = XCreateGC(QTDisplay, QTWindow,
X                GCFunction | GCForeground, &gcv);
X    gcv.function = GXclear;
X    BlackRegion = XCreateGC(QTDisplay, QTWindow,
X                GCFunction | GCForeground, &gcv);
X    puts("Press ENTER to begin");
X    while ('\n' != getchar());
X    if (breadth)
X    BreadthDraw(Tree, width, height);
X    else
X    DepthDraw(Tree, width, height);
X    XSync(QTDisplay, 0);
X    puts("Press ENTER to terminate");
X    while ('\n' != getchar());
X    exit(0);
X}
X
Xdepthdraw(node, x, y, w, h, parent)
XQT_TreeNode_t  *node;
Xint             x, y, w, h, parent;
X{
X    int             color = QT_TreeNode_Color(node), w2, h2;
X    QT_TreeNode_t  *child;
X
X    if (!(ColorsAgree(color, parent))) {
X    if (Verbose) {
X        fprintf(stderr, "Filling (%d,%d) (%dx%d) [%s]\n",
X            x, y, w, h,
X            color ? "black" : "white");
X    }
X    XFillRectangle(QTDisplay, QTWindow,
X               color ? BlackRegion : WhiteRegion,
X               x, y, w, h);
X    }
X    w2 = w >> 1;
X    h2 = h >> 1;
X    if (child = QT_TreeNode_UpperLeft(node)) {
X    depthdraw(child, x, y, w2, h2, color);
X    }
X    if (child = QT_TreeNode_UpperRight(node)) {
X    depthdraw(child, x + w2, y, w - w2, h2, color);
X    }
X    if (child = QT_TreeNode_LowerLeft(node)) {
X    depthdraw(child, x, y + h2, w2, h - h2, color);
X    }
X    if (child = QT_TreeNode_LowerRight(node)) {
X    depthdraw(child, x + w2, y + h2, w - w2, h - h2, color);
X    }
X}
X
XDepthDraw(node, width, height)
XQT_TreeNode_t  *node;
Xint             width, height;
X{
X    depthdraw(node, 0, 0, width, height, 1);
X}
X
XQueueInit()
X{
X    Head = Tail = 0;
X}
X
XQueueAdd(node, x, y, w, h, parent)
XQT_TreeNode_t  *node;
Xint             x, y, w, h, parent;
X{
X    struct Qentry  *result = NewQentry();
X
X    result->node = node;
X    result->x = x;
X    result->y = y;
X    result->width = w;
X    result->height = h;
X    result->parent = parent;
X    result->next = 0;
X    result->prev = Tail;
X    if (Tail)
X    Tail->next = result;
X    Tail = result;
X    if (!Head)
X    Head = result;
X}
X
XQueueDo()
X{
X    struct Qentry  *entry;
X    QT_TreeNode_t  *node, *child;
X    int             x, y, w, h, color, parent, w2, h2;
X
X    for (entry = Head; entry; entry = entry->next) {
X    if (entry->prev)
X        ReleaseQentry(entry->prev);
X    node = entry->node;
X    x = entry->x;
X    y = entry->y;
X    w = entry->width;
X    h = entry->height;
X    color = QT_TreeNode_Color(node);
X    parent = entry->parent;
X    if (!(ColorsAgree(color, parent))) {
X        if (Verbose) {
X        fprintf(stderr, "Filling (%d,%d) (%dx%d) [%s]\n",
X            x, y, w, h,
X            color ? "black" : "white");
X        }
X        XFillRectangle(QTDisplay, QTWindow,
X               color ? BlackRegion : WhiteRegion,
X               x, y, w, h);
X    }
X    w2 = w >> 1;
X    h2 = h >> 1;
X    if (child = QT_TreeNode_UpperLeft(node)) {
X        QueueAdd(child, x, y, w2, h2, color);
X    }
X    if (child = QT_TreeNode_UpperRight(node)) {
X        QueueAdd(child, x + w2, y, w - w2, h2, color);
X    }
X    if (child = QT_TreeNode_LowerLeft(node)) {
X        QueueAdd(child, x, y + h2, w2, h - h2, color);
X    }
X    if (child = QT_TreeNode_LowerRight(node)) {
X        QueueAdd(child, x + w2, y + h2, w - w2, h - h2, color);
X    }
X    }
X}
X
XBreadthDraw(node, width, height)
XQT_TreeNode_t  *node;
Xint             width, height;
X{
X    QueueInit();
X    QueueAdd(node, 0, 0, width, height, 1);
X    QueueDo();
X}
END_OF_xqtdisp.c
if test 5375 -ne `wc -c <xqtdisp.c`; then
    echo shar: \"xqtdisp.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
echo shar: End of shell archive.
exit 0

---- Enclosure ----

______________                  _____________________________
Bob Glickstein                | Internet: [e-mail]
Information Technology Center | Bitnet:   [e-mail]
Carnegie Mellon University    | UUCP:     ...!harvard!andrew.cmu.edu!bobg
Pittsburgh, PA  15213-3890    |
[phone]                | Sinners can repent, but stupid is forever